package com.jietuo.class01;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2024/3/1
 * @description: 4，在一个有序数组中，找某个数是否存在
 */
public class Code04_BSExist {

    public static void main(String[] args) {
        int target = 10;
        int[] arr = new int[]{5, 6, 7, 10, 12, 14};
        boolean b = someOneIsExist(arr, target);
        System.out.println(b);
    }

    /**
     * 有序数组，可以使用二分查找
     * step1: 先找出数组中点， n/2
     * step2: 拿出中点的数和目标数比较，大了，则往右继续找，在找右边的中点 (n/2 + 1 +n-1)/2
     * step3: 继续，直到找到这个数
     *
     * @param arr    有序数组
     * @param target 某个数
     * @return 是否存在
     */
    public static boolean someOneIsExist(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target < arr[mid]) {
                right = mid - 1;
            }
            if (target > arr[mid]) {
                left = mid + 1;
            }
            mid = (left + right) / 2;
            if (target == arr[mid]) {
                return true;
            }
        }
        return arr[left] == target;
    }
}
